package com.hard;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 做困难题即是一种折磨又是一种享受
 * 极角排序
 *
 * atan2()函数是atan的升级版，可以确定象限
 *
 * 返回 y/x 的反正切值，以弧度表示，取值范围为(-π,π]。如上图所示，tan(θ) = y/x，θ = atan2(y, x)。
 *
 * 当 (x, y) 在象限中时：
 * 当 (x, y) 在第一象限，0 < θ < π/2
 * 当 (x, y) 在第二象限，π/2 < θ ≤ π
 * 当 (x, y) 在第三象限，-π < θ < -π/2
 * 当 (x, y) 在第四象限，-π/2 < θ < 0
 *
 * 当 (x, y) 在象限的边界（也就是坐标轴）上时：
 * 当 y 是 0，且 x 为非负值，θ = 0
 * 当 y 是 0，且 x 是负值，θ = π
 * 当 y 是正值，且 x 是 0，θ = π/2
 * 当 y 是负值，且 x 是 0，θ = -π/2
 *
 *
 * 1610. 可见点的最大数目
 * 给你一个点数组 points 和一个表示角度的整数 angle ，你的位置是 location ，其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。
 *
 * 最开始，你面向东方进行观测。你 不能 进行移动改变位置，但可以通过 自转 调整观测角度。换句话说，posx 和 posy 不能改变。你的视野范围的角度用 angle 表示， 这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-number-of-visible-points
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月16日 14:23
 */
public class VisiblePoints {

    double eps = 1e-9;

    /**
     * 解决该题，考虑两个方面
     * 1、极角排序
     * 2、滑动窗口
     *
     * @param points
     * @param angle
     * @param location
     * @return
     */
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int x = location.get(0), y = location.get(1);
        List<Double> list = new ArrayList<>();
        // 与我们的极点一样的点个数
        int cnt = 0;
        // 将角度
        double pi = Math.PI, t = angle * pi / 180;
        for (List<Integer> p : points) {
            int a = p.get(0), b = p.get(1);
            if (a == x && b == y && ++cnt >= 0) continue;
            // 将结果从（-pi,pi）映射到(0,2pi)
            list.add(Math.atan2(b - y, a - x) + pi);
            // atan2 与可以由atan（）分情况讨论得来
        }
        Collections.sort(list);



        int n = list.size(), max = 0;
        // 4象限可能和1象限混合，所有要进行拼接
        // 在求连续段长度时，先对夹角数组进行拷贝拼接，并对拼接部分增加偏移量（确保数组仍具有单调性）。
        // 具体的，设夹角数组长度为 nn，此时令 list[n + i] = list[i] + 2 * PIlist[n+i]=list[i]+2∗PI，从而将问题彻底转换为求连续段问题
        //
        //作者：AC_OIer
        //链接：https://leetcode-cn.com/problems/maximum-number-of-visible-points/solution/gong-shui-san-xie-qiu-ji-jiao-ji-he-ti-b-0bid/
        //来源：力扣（LeetCode）
        //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        for (int i = 0; i < n; i++) list.add(list.get(i) + 2 * pi);
        for (int i = 0, j = 0; j < 2 * n; j++) {
            // 缩小窗口,
            while (i < j && list.get(j) - list.get(i) > t + eps) i++;
            // 增大窗口
            max = Math.max(max, j - i + 1);
        }
        return cnt + max;
    }


}
